import { btPrint } from "hy-algokit";
import bsTree from "./bsTree3";

import { TreeNode } from "./bsTree3";

export default class AVLTreeNode<T> extends TreeNode<T> {
  left: AVLTreeNode<T> | null = null;
  right: AVLTreeNode<T> | null = null;
  parent: AVLTreeNode<T> | null = null;

  height: number = this.getHeight(); // 节点高度
  // 获取节点高度，就是去左右节点最大高度加一，动态变化是最佳实现
  getHeight(): number {
    const leftHeight = this.left?.getHeight() || 0;
    const rightHeight = this.right?.getHeight() || 0;
    return Math.max(leftHeight, rightHeight) + 1;
  }
  // 获取权重，左右节点高度的差-1至1，才算平衡
  getBalanceFactor(): number {
    const leftHeight = this.left?.getHeight() || 0;
    const rightHeight = this.right?.getHeight() || 0;
    return leftHeight - rightHeight;
  }
  // 判断当前节点是否平衡
  get isBalanced(): boolean {
    const factor = this.getBalanceFactor();
    return factor >= -1 && factor <= 1;
  }

  // 更高的子节点
  get hightChild(): AVLTreeNode<T> | null {    
    const leftHeight = this.left?.getHeight() || 0;
    const rightHeight = this.right?.getHeight() || 0;
    
    if (leftHeight < rightHeight) return this.right;
    if (leftHeight > rightHeight) return this.left;
    // 相等的情况下也不会返回null，而是看当前节点是左还是右节点来返回对应的子节点
    return this.isLeft ? this.left : this.right;
  }

  // 右旋转
  rightRation() {
    // 确定当前节点是左节点还是右节点
    const isLeft = this.isLeft;
    const isRight = this.isRight;

    // 1. 处理pivot节点（找到轴心，轴心的父节点要换指向）
    const pivot = this.left!;
    pivot.parent = this.parent;
    // 2. 处理pivot的右节（断开了当前节点的左指向连到轴心的右节点上，如果有值父类的节点执行也有改好，这个时候轴心和当前节点已经没有瓜葛了）
    this.left = pivot.right;
    if (pivot.right) {
      pivot.right!.parent = this;
    }
    // 3. 处理this（当前节点挂载到轴心节点上，低了一头了）
    pivot.right = this;
    this.parent = pivot;
    // 4. 挂载pivot（到这一步开始为止，轴心是指向了父级，但是父级的指向还是当前节点，所以要改父级的指向）
    if (!pivot.parent) return pivot;
    if (isLeft) {
      pivot.parent!.left = pivot;
    } else if (isRight) {
      pivot.parent!.right = pivot;
    }
    return pivot;
  }
  // 左旋转
  leftRation() {
    // 确定当前节点是左节点还是右节点
    const isLeft = this.isLeft;
    const isRight = this.isRight;

    // 1. 处理pivot节点（找到轴心，轴心的父节点要换指向）
    const pivot = this.right!;
    pivot.parent = this.parent;
    // 2. 处理pivot的右节（断开了当前节点的左指向连到轴心的右节点上，如果有值父类的节点执行也有改好，这个时候轴心和当前节点已经没有瓜葛了）
    this.right = pivot.left;
    if (pivot.left) {
      pivot.left!.parent = this;
    }
    // 3. 处理this（当前节点挂载到轴心节点上，低了一头了）
    pivot.left = this;
    this.parent = pivot;
    // 4. 挂载pivot（到这一步开始为止，轴心是指向了父级，但是父级的指向还是当前节点，所以要改父级的指向）
    if (!pivot.parent) return pivot;
    if (isLeft) {
      pivot.parent!.left = pivot;
    } else if (isRight) {
      pivot.parent!.right = pivot;
    }
    return pivot;
  }
}

// 右旋转测试
// const avlNode1 = new AVLTreeNode(10);
// avlNode1.left = new AVLTreeNode(8);
// avlNode1.left.left = new AVLTreeNode(5);
// const parent = new AVLTreeNode(12);
// parent.left = avlNode1;
// avlNode1.parent = parent
// avlNode1.left.parent = avlNode1
// avlNode1.left.left.parent = avlNode1.left
// btPrint(parent)
// avlNode1.rightRation()
// btPrint(parent)

// 左旋转测试
// const avlNode1 = new AVLTreeNode(10);
// avlNode1.right = new AVLTreeNode(8);
// avlNode1.right.right = new AVLTreeNode(5);
// const parent = new AVLTreeNode(12);
// parent.left = avlNode1;
// avlNode1.parent = parent;
// avlNode1.right.parent = avlNode1;
// avlNode1.right.right.parent = avlNode1.left;
// btPrint(parent);
// avlNode1.leftRation();
// btPrint(parent);


// console.log(avlNode1.hightChild);
